向量检索与 ANN 索引
11-RAG 检索增强 讲的是整条生成链路，这一篇只讲其中检索侧的核心机制：向量之间的远近怎么算、为什么必须用近似检索、主流索引各自在做什么、top-k 怎么取。
先纠正一个定位：向量检索是 RAG 检索侧的一种方法，不是全部。 检索侧至少还有这几种，生产上常混用：
| 方法 | 依据 | 强项 | 弱项 |
|---|---|---|---|
| 稠密向量检索 | 语义相似度 | 同义改写、跨表述匹配 | 专有名词、精确 ID 匹配差 |
| 稀疏检索（BM25 等） | 词项匹配 | 公司名、财务指标、会计期间这类逐字出现的术语 | 不会语义泛化 |
| 图检索 | 实体与关系 | 多跳关系推理 | 要有图谱，构建成本高 |
| 结构化查询 | SQL / 元数据 | 精确、可聚合 | 只能问出已知模式 |
| 混合检索 | 多路融合 | 覆盖面最广 | 需要融合策略（见 11-RAG 检索增强 的 RRF） |
所以「RAG 效果不好」时，第一件该判断的事是：我的查询适合哪一路？ 拿专有名词去问纯向量库，本来就不该期待好结果。
距离怎么算
向量之间「近」的定义决定了索引怎么建，三种主流度量：
| 度量 | 含义 | 典型场景 |
|---|---|---|
| L2 欧氏距离 | 两点间直线距离：各维差值平方和再开根号 | 视觉特征、度量学习 |
| 余弦相似度 | 只看方向夹角，不看模长；方向完全一致为 1 | 文本语义检索——语义更关心「话题方向」而非向量长短 |
| 内积（点积） | 余弦的未归一化版本 | 推荐系统——模长可以顺手编码「热度」 |
一个实用的工程冷知识：向量先做 L2 归一化，内积就等于余弦相似度。所以 FAISS 里用 IndexFlatIP 配归一化向量，算的其实就是余弦。
不过最终应以具体模型的模型卡和训练目标为准——有些嵌入模型是按内积训练的，硬套余弦反而错。
为什么不能用 B+ 树
「给向量建个索引」的第一反应是 B+ 树或哈希表，但两者都不行：
| 结构 | 为什么不行 |
|---|---|
| B+ 树 | 它依赖数据有稳定的「大小顺序」——数字、字符串是一维的，能排序。向量是上千维浮点数组，很难定义一个既自然又能服务相似度查询的全序关系 |
| 普通哈希 | 依赖精确等值命中，而两个浮点向量完全相等的概率约等于零，无法表达「相近」 |
| — | 高维空间中的维度灾难会让许多传统低维索引结构逐渐失去效率 |
LSH（局部敏感哈希）是专门为近似相似检索设计的另一类 ANN 方法，和普通哈希不是一回事。
退到暴力搜索（Brute-Force）呢？它对，但代价是 O(N × dim)：
def brute_force_search(vectors, query, k=10):
scores = vectors @ query # 归一化后内积 = 余弦相似度
return np.argsort(-scores)[:k] # 分数降序，取前 K算笔账：100 万条 1024 维向量，一轮查询约 20 亿次浮点运算；光把这 4GB 向量从内存读一遍就要吃掉可观的内存带宽，放磁盘上更是灾难。100 个并发用户就把 CPU 排到天亮。
数据量小的时候暴力搜索就是最优解——结果 100% 精确，连索引都不用建。ANN 是数据量上来之后才必须付的代价。
ANN：用少量召回换数量级速度
ANN（Approximate Nearest Neighbor，近似最近邻） 不保证返回全局最优的 K 个近邻，而是靠预建索引只扫描一小部分向量，返回「足够接近」的结果。
典型的交易是：recall@10 保持在 95–99%，把延迟从秒级压到毫秒级。
recall@K 的常见误解
看到「95% 召回率」就以为「5% 的查询会彻底失败」，是错的。recall@K 描述的是整体结果的平均重合程度，不是「有多少比例的查询完全失效」。
对 RAG 来说，边界位置的少量交换通常影响有限——反正下游模型还要再读一遍上下文。但真正重要的答案没进候选集，仍会影响最终回答。
反过来，人脸支付、重复内容去重这类「漏一个就是事故」的业务，要单独针对 recall@1 设计指标，不能拿 recall@10 的 95% 自我安慰。
三大件的分工（这个区分最容易被搞混）
┌─────────────────────────────────────────────────┐
│ 问题一：搜哪些向量？（路由） │
│ ├─ IVF 聚类分区派：切 nlist 个簇，只探 nprobe 个 │
│ └─ HNSW 图导航派：沿多层近邻图下钻 │
└─────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────┐
│ 问题二：每条向量怎么用更少的字节表示？（压缩） │
│ └─ PQ 把高维向量切段，每段用聚类中心编号替代 │
└─────────────────────────────────────────────────┘
PQ 严格来说是一种量化压缩方法，不负责路由。
它通常与 IVF 或 HNSW 组合使用（IVF-PQ、HNSW-PQ），而不是单独承担检索。
三者的关系：两种路由机制各选一个，压缩按需要叠加。PQ 严格来说是一种量化压缩方法，不负责路由。 它通常与 IVF 或 HNSW 组合使用（IVF-PQ、HNSW-PQ），而不是单独承担检索。三者可以叠加。
HNSW：图导航
HNSW（Hierarchical Navigable Small World，分层可导航小世界图） 是目前最广泛部署的 ANN 索引——pgvector、Qdrant、Weaviate、Milvus、FAISS 以及多数托管向量库的默认选项。
结构：三层路网
把向量组织成一张多层近邻图，层数越高节点越少、连接越长：
HNSW 把向量组织成一张多层近邻图：层数越高节点越少、连接越长
顶层 高铁网 全国几十个站，站间一跳上千公里
│ └─ 查询从这里进入，先粗定位到大区域
▼
中层 城际地铁 上百个站，送进目标片区
│
▼
底层 街道 所有向量都在这一层，负责最后一百米的精确定位
└─ 到底层后维护一个候选集做更充分的搜索
查询的走向
从顶层某个入口出发 ──▶ 反复查看邻居、移动到更接近目标的节点
──▶ 该层无法继续改善时下沉一层
──▶ 重复到最底层 ──▶ 返回最近的 K 个
复杂度约 O(log N)，而不是 O(N)。
三个参数
M 每节点每层最多连几条边（部分实现底层放宽到 2M） 16–32
efConstruction 建图时的候选集宽度 100–200
efSearch 查询时的候选集宽度 32–128，不小于 K
└─ efSearch 是运行时的召回/延迟旋钮，不需要重建索引就能调 ——
HNSW 最实用的一点查询时从顶层某个入口出发，在每层反复查看邻居、移动到更接近目标的节点，直到该层无法继续改善，再带着当前结果下沉到下一层。到底层后维护一个候选集做更充分的搜索，最后返回最近的 K 个。
复杂度约 O(log N)，而不是 O(N)。
三个参数
| 参数 | 作用 | 典型值 | 调大的收益与代价 |
|---|---|---|---|
| M | 每个节点每层最多连几条边（部分实现的底层会放宽到 2M） | 16–32（也有 16–64 的说法） | 边越密召回越高；内存和建图时间同步上涨 |
| efConstruction | 建图时的候选集宽度 | 100–200 | 图的质量更好，建图更慢 |
| efSearch | 查询时的候选集宽度 | 32–128，工程上一般不小于 K | 召回更高，延迟更大 |
efSearch 是运行时的召回/延迟旋钮——不需要重建索引就能调。这是 HNSW 最实用的一点。
实测的三档配置（1M × 1536 维）
| 配置（M / efSearch） | Recall@10 | 查询延迟 | 吞吐 |
|---|---|---|---|
| 快（16 / 32） | 93.4% | 1.1 ms | 3,850 QPS |
| 均衡（32 / 64） | 97.8% | 2.2 ms | 2,100 QPS |
| 高精度（64 / 128） | 99.4% | 4.6 ms | 1,050 QPS |
三档配置在召回、延迟、吞吐上的实测权衡（1M × 1536 维）。
M / efSearch Recall@10 延迟 吞吐
快 16 / 32 93.4% 1.1 ms 3,850 QPS
均衡 32 / 64 97.8% 2.2 ms 2,100 QPS
高精度 64 / 128 99.4% 4.6 ms 1,050 QPS
召回从 93.4% 提到 99.4%（+6 个百分点）的代价是延迟 ×4、吞吐掉到 27%。
└─ 最后那 1.6 个百分点（97.8 → 99.4）单独占掉了接近一半的延迟预算。
两条必须知道的代价
内存是它的价签
M = 16 + 768 维 FP32 ──▶ 每个向量约 3.4 KB（向量 + 图边 + 开销）
│
└─ 1 亿向量就是 340 GB DRAM，还没算应用层开销
└─ 经验规律：HNSW 在 1000 万到 5000 万向量以下是正确答案，
到十亿级就是错误答案
删除是墓碑
删节点会破坏图结构，实现上通常只置一个 DELETE_MARK 位、查询时跳过
│
└─ 长期下来小世界性质退化，recall 会从 98% 掉到 85% 甚至更低
高变更（churn）场景需要定期重建索引两个必须知道的代价
内存是它的价签。 图结构要常驻内存：向量存一份，每个节点几十条边的邻居编号又是一份。M=16 + 768 维 FP32，每个向量约 3.4 KB（向量 + 图边 + 开销）；1 亿向量就是 340 GB DRAM，还没算应用层开销。
所以有一条经验规律：HNSW 在 1000 万到 5000 万向量以下是正确答案，到十亿级就是错误答案。
删除是墓碑。 删节点会破坏图结构，所以实现上通常只置一个 DELETE_MARK 位、查询时跳过。长期下来小世界性质退化，recall 会从 98% 掉到 85% 甚至更低——高变更（churn）场景需要定期重建索引。
IVF：聚类分区
IVF（Inverted File Index） 先用 K-Means 把向量空间切成 nlist 个簇，每个簇一个质心；查询时只探测离查询向量最近的 nprobe 个簇，簇内再算精确距离。
类比快递分拨：包裹不会被送到全国每个网点问「这是谁的」，而是先到目标城市的分拨中心，再层层下沉。
省多少：1000 万条向量、nlist=4096、nprobe=32 时，平均扫描约 32/4096 ≈ 0.8%——候选集从一千万压到八万。
两个旋钮的脾气
| 参数 | 作用 | 经验取值 |
|---|---|---|
| nlist | 簇数 | √N 到 4√N 作为初始试探范围，但不是硬公式。簇越多每簇越小、扫描量可能下降，但训练与质心搜索成本上升，边界召回更敏感 |
| nprobe | 探测簇数 | nlist/32 到 nlist/8 对应 90–95% 召回。FAISS 的默认 nprobe=1 在生产里几乎总是错的 |
软肋：聚类边界是硬切割
查询向量恰好站在两个簇的界线上、真正的最近邻躺在隔壁簇里，而你没探测那个簇——它就根本进不了这次查询的候选集。这不是「排得靠后」，是「完全没出现」，重排阶段也救不回来。
数据分布严重不均、某些簇过大时效果也会打折。另外 K-Means 要先训练，数据持续涌入、分布漂移后通常需要重训或调整，增量更新不如 HNSW 方便。
PQ：压缩，不是索引
PQ（Product Quantization，乘积量化） 把高维向量切成若干段，每段独立用聚类中心编号替代原始浮点值。
三步
① 切段
把 D 维向量均匀切成 M 段（128 维切 16 段，每段 8 维）
│
▼
② 子空间聚类
对每段子向量单独跑 K-Means，通常聚 256 个中心
└─ 256 = 2⁸，所以每段编号正好用 1 字节
│
▼
③ 编码
每段用 1 字节编号（0–255）替代原来的 8 个浮点数
压缩比
128 维切 16 段 512 字节 ──▶ 16 字节 （32 倍）
1536 维切 64 段 6144 字节 ──▶ 64 字节 （96 倍）
4096 维切 64 段 16 KB ──▶ 64 字节
代价：编号是中心的近似，量化误差天生存在。
所以 PQ 的产出只配当「粗排分」，不能当最终结论。压缩比：128 维从 512 字节 → 16 字节（32 倍）；1536 维切 64 段，6144 字节 → 64 字节（96 倍）；4096 维切 64 段，16 KB → 64 字节。
ADC：为什么它能快到这种程度
压成编号之后，距离怎么算？这是 PQ 最巧妙的部分——ADC（Asymmetric Distance Computation，非对称距离计算）：
- 查询向量不压缩，照样切成 M 段
- 预先算好每段查询子向量到该段 256 个中心的距离，拼成一张 M × 256 的查找表
- 库里的向量只存着 M 个编号，近似距离 = 查 M 次表、加起来
浮点乘加变成了查表加法——这就是亿级向量粗排能跑在普通机器上的原因。
两个实现细节
残差编码：实际的 IVF-PQ 里，常见做法是先减去所属簇的质心、对残差向量做 PQ 编码，而不是去直接量化原始向量，这能进一步降低量化误差。
OPQ（Optimized PQ）：量化前先旋转向量空间以最小化重构误差。需要离线训练，但同压缩比下召回能提升 2–5%。
代价：编号是中心的近似，量化误差天生存在。所以 PQ 的产出只配当「粗排分」，不能当最终结论——下一节马上要用到这句。
DiskANN：单机十亿级
DiskANN 的思路是分层用存储：Vamana 图与全精度向量放 SSD，只把 PQ 压缩向量放 RAM 供遍历使用。
- 构建用 α-relaxed pruning（α > 1），产生比 HNSW 的严格多样性启发式更长距离的边，减少图的跳数
- 一次查询：先在 RAM 里对 PQ 向量做 beam search 找出候选，再对它们的全精度向量发起 5–10 次 SSD 随机读做重排
- 瓶颈是 SSD 带宽，不是容量
SIFT1B 基准（10 亿 × 128 维）上，16 核 / 64 GB RAM / 一块消费级 SSD 能跑 5000+ QPS、平均延迟 < 3 ms、95%+ 1-recall@1。同样语料用 HNSW 需要 640+ GB RAM。
ScaNN
Google 2020 年的 ScaNN 用的是各向异性量化（anisotropic quantization）——按各维度对内积排名的贡献加权，而不是像 PQ 那样对各维度一视同仁。发布时在 ann-benchmarks 上超过了其他 11 个调优过的库（同等召回下约 2 倍 QPS）。
怎么选
| 判据 | Flat（暴力） | IVF | HNSW | PQ |
|---|---|---|---|---|
| 数据量 | < 100K | 100K–10M | 100K–50M | 1M–1B+ |
| 召回 | 100% | 90–99% | 95–99.9% | 80–95% |
| 内存 | 高 | 高 | 很高 | 低 |
| 建索引 | 无 | 中等 | 慢 | 中等 |
| 查询速度 | 规模化后很慢 | 快 | 很快 | 快 |
| 增量插入 | 支持 | 需重建 | 原生支持 | 需重建 |
多数场景的默认答案：向量数少于 1000 万时选 HNSW——召回最高、查询速度有竞争力、且不需要训练步骤。
三类特殊情形：
- 内存不够 → 加 PQ 压缩（IVF-PQ、HNSW-PQ），代价是召回
- 十亿级 → DiskANN 那类磁盘图方案，或 IVF-PQ
- 要求绝对精确 → Flat，但只在 10 万向量以下才现实
四种索引的对照，判据以数据量为入口。
Flat IVF HNSW PQ
数据量 < 100K 100K–10M 100K–50M 1M–1B+
召回 100% 90–99% 95–99.9% 80–95%
内存 高 高 很高 低
建索引 无 中等 慢 中等
查询速度 规模化后慢 快 很快 快
增量插入 支持 需重建 原生支持 需重建
└─ 多数场景的默认答案：向量数少于 1000 万时选 HNSW ——
召回最高、查询速度有竞争力，而且不需要训练步骤。
三类特殊情形
内存不够 ──▶ 加 PQ 压缩（IVF-PQ、HNSW-PQ），代价是召回
十亿级 ──▶ DiskANN 那类磁盘图方案，或 IVF-PQ
要求绝对精确 ──▶ Flat，但只在 10 万向量以下才现实
怎么测自己的 recall
① 用 Flat 索引对一批代表性 query 跑出真值（精确最近邻）
② 再拿 ANN 索引跑同样的 query
③ recall@K = 真近邻出现在 ANN 结果里的比例
└─ 95% 表示平均每条查询的真实 Top-K 里有 9.5 个被找回
└─ 别信任何脱离数据的「默认参数」怎么测自己的 recall
用 Flat 索引对一批代表性 query 跑出真值（精确最近邻），再拿 ANN 索引跑同样的 query，算 recall@K = 真近邻出现在 ANN 结果里的比例。95% 表示平均每条查询的真实 Top-K 里有 9.5 个被找回。
别信任何脱离数据的「默认参数」。
top-k 怎么取
top-k 不是一个可以拍脑袋定的常数，它受四个因素牵制：
| 因素 | 影响 |
|---|---|
| 下游要几条 | 最终送进模型的是 3–5 条（见 11-RAG 检索增强 的两阶段规则），所以 k 要按「召回多少给重排」定，不是按「送几条」定 |
| 重排器的容量 | 重排 100 条以上的候选很少划算——这是 k 的上界来源 |
efSearch / nprobe 的下界 | HNSW 的 efSearch 不应小于 k，否则候选集比要的还小；IVF 同理 |
| 延迟预算 | 加 k 是线性加成本：更多候选 = 更多重排推理 + 更多 token |
工程上的取法，按顺序做三件事：
- 定最终条数 n（由模型的上下文预算和答案粒度决定，通常 3–5）
- 定召回放大倍数，取
k = n × 放大倍数。放大倍数按「重排能捞回多少」定——检索是粗的、重排是精的，所以要给它足够的选择余地。扩到 4 倍是个常见的起点（HelloAgents 的candidate_pool_multiplier默认就是 4） - 设一个绝对下限，防止 n 很小时候选池太小。同样在 HelloAgents 里是
max(top_k × multiplier, 20)
另外两个和 top-k 配套的机制：
分数阈值：在 top-k 之外再加一个 score_threshold，低于它的结果直接丢掉。它在硬约束场景下有特殊价值——如果连最高分都不够高，正确行为是拒答而不是硬答（对应 11-RAG 检索增强 里的置信度门控）。
去重合并：多路检索或查询扩展会产生重复，合并时按 document id 保留最高分（RRF 里也是这个逻辑），最后再截到 k。
top-k 受四个因素牵制，取法按三步走。
四个牵制因素
下游要几条 最终送进模型的是 3–5 条
└─ 所以 k 要按「召回多少给重排」定，不是按「送几条」定
重排器的容量 重排 100 条以上很少划算 —— 这是 k 的上界来源
efSearch / nprobe HNSW 的 efSearch 不应小于 k，否则候选集比要的还小
IVF 的 nprobe 同理
延迟预算 加 k 是线性加成本：更多候选 = 更多重排推理 + 更多 token
取法（按顺序）
① 定最终条数 n 由模型的上下文预算与答案粒度决定，通常 3–5
│
▼
② 定召回放大倍数 k = n × 倍数 给重排留选择余地，扩到 4 倍是个常见的起点
│
▼
③ 设一个绝对下限 防止 n 很小时候选池太小：max(k, 20)
两个配套机制
分数阈值 score_threshold 低于它直接丢掉。硬约束场景下有特殊价值 ——
连最高分都不够高时，正确行为是拒答而不是硬答
去重合并 多路检索或查询扩展会产生重复，
按 document id 保留最高分，最后再截到 k一条查询的完整旅程
把前面的零件拼起来（以「带标量过滤 + IVFPQ」为例）：
① 向量化 用户提问 → embedding 模型 → 查询向量
│
▼
② 标量过滤 用元数据剔掉不符合条件的候选（"只查 2026 年之后的"）
│ └─ 最容易被忽略、但生产里天天用的一步
▼
③ ANN 粗筛 IVF 探 nprobe 个簇 / HNSW 沿图下钻
│ 从百万级捞出几百到几万个「大概近」的
▼
④ PQ 粗排 用查表距离快速打分排序（便宜但粗糙）
│
▼
⑤ 原始向量精排 取前几百名捞回原始 FP32 向量，算精确距离重排
│
▼
送进重排器 / prompt
反直觉的一点：在需要精排的方案里，近似索引通常只负责海选，
决赛还是原始浮点向量之间的比较。
└─ 由此推出一条部署约束：精排意味着系统还得保存原始向量，
或者能从外部存储回捞。量化索引必须额外考虑原始向量放在哪 ——
这也是 DiskANN 要在 SSD 上留一份全精度向量的原因。反直觉的一点：在需要精排的方案里，近似索引通常只负责海选，决赛还是原始浮点向量之间的比较。
由此推出一个部署上的约束：精排意味着系统还得保存原始向量，或者能从外部存储回捞。如果索引本身存的就是原始向量（Flat、HNSW、IVF-FLAT），向量本身就是结果；如果是量化索引，就必须额外考虑原始向量的存放位置——这也是 DiskANN 要在 SSD 上留一份全精度向量的原因。
第 ② 步是最容易被忽略、但生产里天天用的：带过滤的向量检索（filtered search）在实现上有三种取舍——先过滤再搜（过滤后可能太小）、边搜边过滤（实现复杂）、先搜后过滤再扩大候选集（要多取一些）。选哪种取决于过滤条件的选择性有多强。
相关
- 11-RAG 检索增强 —— 这篇的算法层服务于那条六阶段链路
- 10-智能体记忆系统 —— 同一套向量存储，靠元数据字段隔离命名空间
- 05-文本分词与子词算法：BPE、WordPiece 与 Unigram —— 向量化的上游：文本先要过 tokenizer
参考
- https://www.nexprotools.com/blog/vector-database-indexing-hnsw-ivf-pq-ann-search-guide
- https://hld.handbook.academy/curriculum/ai-ml-system-design/vector-search-at-scale
- https://callsphere.ai/blog/vector-index-types-flat-ivf-hnsw-product-quantization
- https://www.machinelearningatscale.com/blog/hnsw-ann-vector-search-explained
- https://aiengineeringfromscratch.com/lesson.html?path=phases/11-llm-engineering/07-advanced-rag
YJ